/*
 * @Author       : wangzeyu 2309335887@qq.com
 * @Date         : 2023-07-23 20:53:11
 * @LastEditors  : WangZeYu
 * @LastEditTime : 2023-07-23 22:20:54
 * @FilePath     : \my-study-js\algorithm\greedy.js
 * @Description  : 分数背包问题(贪心算法 Greedy Algorithm)
 */

function greedy(weights, values, capacity) {
  let list = []
  for (let i = 0; i < weights.length; i++) {
    list.push({
      number: i + 1,
      weight: weights[i],
      value: values[i],
      vRate: values[i] / weights[i],
    })
  }
  list.sort((a, b) => {return b.vRate - a.vRate })
  console.log('list',list);
  
  let selects = []
  let total = 0
  for (let i = 0; i < list.length; i++) {
    if (list[i].weight < capacity) {
      selects.push({
        number: list[i].number,
        weight: list[i].weight,
        value: list[i].value,
        vRate:list[i].vRate,
        rate: 1,
      })
      total += list[i].value
      capacity -= list[i].weight
    } else if (list[i].weight > capacity) {
      selects.push({
        number: list[i].number,
        weight: list[i].weight,
        value: list[i].value,
        vRate:list[i].vRate,
        rate: capacity / list[i].weight,
      })
      total += (capacity / list[i].weight) * list[i].value
      break
    } else {
      selects.push({
        number: list[i].number,
        weight: list[i].weight,
        value: list[i].value,
        vRate:list[i].vRate,
        rate: 1,
      })
      total += list[i].value
      break
    }
  }

  console.log('总价值为:', total);
  console.log('选择的物品为:', selects);
}
let weights = [2, 2, 6, 5, 4]
let values = [6, 3, 5, 4, 6]
greedy(weights, values, 10)